Jump to content

Partial cyclic order

From Wikipedia, the free encyclopedia

In mathematics, a partial cyclic order is a ternary relation that generalizes a cyclic order in the same way that a partial order generalizes a linear order.

Definition

[edit]

Over a given set, a partial cyclic order is a ternary relation that is:

  • cyclic, i.e. it is invariant under a cyclic permutation:
  • asymmetric:
  • transitive: and [1]

Constructions

[edit]

Direct sum

Direct product

Power[2][3]

Dedekind–MacNeille completion

Extensions

[edit]

linear extension, Szpilrajn extension theorem

standard example

The relationship between partial and total cyclic orders is more complex than the relationship between partial and total linear orders. To begin with, not every partial cyclic order can be extended to a total cyclic order. An example is the following relation on the first thirteen letters of the alphabet: {acd, bde, cef, dfg, egh, fha, gac, hcb} ∪ {abi, cij, bjk, ikl, jlm, kma, lab, mbc}. This relation is a partial cyclic order, but it cannot be extended with either abc or cba; either attempt would result in a contradiction.[4]

The above was a relatively mild example. One can also construct partial cyclic orders with higher-order obstructions such that, for example, any 15 triples can be added but the 16th cannot. In fact, cyclic ordering is NP-complete, since it solves 3SAT. This is in stark contrast with the recognition problem for linear orders, which can be solved in linear time.[5][6]

Notes

[edit]

References

[edit]
  • Galil, Zvi; Megiddo, Nimrod (October 1977), "Cyclic ordering is NP-complete" (PDF), Theoretical Computer Science, 5 (2): 179–182, doi:10.1016/0304-3975(77)90005-6, retrieved 30 April 2011
  • Megiddo, Nimrod (March 1976), "Partial and complete cyclic orders" (PDF), Bulletin of the American Mathematical Society, 82 (2): 274–276, doi:10.1090/S0002-9904-1976-14020-7, retrieved 30 April 2011
  • Novák, Vítězslav (1982), "Cyclically ordered sets" (PDF), Czechoslovak Mathematical Journal, 32 (3): 460–473, doi:10.21136/CMJ.1982.101821, hdl:10338.dmlcz/101821, retrieved 30 April 2011
  • Novák, Vítězslav; Novotný, Miroslav (1984a), "On a power of cyclically ordered sets" (PDF), Časopis Pro Pěstování Matematiky, 109 (4): 421–424, doi:10.21136/CPM.1984.118209, hdl:10338.dmlcz/118209, retrieved 30 April 2011
  • Novák, Vítězslav; Novotný, Miroslav (1984b), "Universal cyclically ordered sets" (PDF), Czechoslovak Mathematical Journal, 35 (1): 158–161, doi:10.21136/CMJ.1985.102004, hdl:10338.dmlcz/102004, retrieved 30 April 2011

Further reading

[edit]